import { ListNode } from "../dataClass";

/**
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
 */
(function () {
    /**
     * Definition for singly-linked list.
     * class ListNode {
     *     val: number
     *     next: ListNode | null
     *     constructor(val?: number, next?: ListNode | null) {
     *         this.val = (val===undefined ? 0 : val)
     *         this.next = (next===undefined ? null : next)
     *     }
     * }
     */

    /**
     * @description 解法1，设定新链表，两个指针(分别指向l1, l2)，同时遍历l1与l2，当l1的当前值大于l2的当前值是，新链表的next指向l2，同时l2的指针后移，反之则新链表的next指向l1，同时l1的指针后移
     * 注意点：
     * 1. 需要设置新链表的初始值
     * 2. 需要设置头结点指向新链表
     * @param l1
     * @param l2
     * @returns
     */
    function mergeTwoLists(
        l1: ListNode | null,
        l2: ListNode | null
    ): ListNode | null {
        let list: ListNode | null = null;
        let ret: ListNode | null = null;
        if (!l1 && !l2) return list;
        else if (!l1) return l2;
        else if (!l2) return l1;

        if (l1.val > l2.val) {
            list = l2;
            l2 = l2.next;
        } else {
            list = l1;
            l1 = l1.next;
        }
        ret = list;

        while (l1 || l2) {
            if (!l1) {
                list.next = l2;
                break;
            } else if (!l2) {
                list.next = l1;
                break;
            }

            if (l1.val > l2.val) {
                list.next = l2;
                l2 = l2.next;
            } else {
                list.next = l1;
                l1 = l1.next;
            }
            list = list.next;
        }

        return ret;
    }
})();

(function () {
    /**
     * @description 递归法
     * @param l1
     * @param l2
     * @returns
     */
    function mergeTwoLists(
        l1: ListNode | null,
        l2: ListNode | null
    ): ListNode | null {
        if (!l1 && !l2) return null;
        else if (!l1) return l2;
        else if (!l2) return l1;

        if (l1.val > l2.val) {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        } else {
            l1.next = mergeTwoLists(l1.next, l2);
            return l2;
        }
    }
})();
